package link;

import offer.TreeNode;

/**
 * 给你单链表的头指针 head 和两个整数 left 和 right ，
 * 其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 */
public class leetCode92_reverseBetween {

    public static void main(String[] args) {
        leetCode92_reverseBetween a = new leetCode92_reverseBetween();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode listNode = a.reverseBetween(head, 2, 4);
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null) return null;
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode preNode = pre;
        ListNode rightNode = pre;
        int i = 1;
        int j = 0;
        while (i < left){
            preNode = preNode.next;
            i++;
        }
        while (j < right){
            rightNode = rightNode.next;
            j++;
        }

        ListNode leftNode = preNode.next;
        ListNode postNode = rightNode.next;

        preNode.next = null;
        rightNode.next = null;

        reverse(leftNode);

        preNode.next = rightNode;
        leftNode.next = postNode;

        return pre.next;

    }

    public void reverse(ListNode head){
        if(head == null) return;
        ListNode cur = head;
        ListNode pre = null;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}